#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

void libera_matriz (int m, int n, int **v){
  	int  i;  
 	for (i=0; i<m; i++) free (v[i]); 	
	free (v);      
}

int **aloca_matriz(int m, int n) {
	int **v; 
	int i;    
	if (m < 1 || n < 1) { 
		printf("Erro: Parametro invalido");
		return NULL;
	}

	v = (int **) malloc (m * sizeof(int *));
	if (v == NULL) {
		printf("Erro: Memoria Insuficiente");
		return NULL;
	}

	for (i = 0; i < m; i++) {
		v[i] = (int*) malloc (n * sizeof(int));
		if (v[i] == NULL) {
			printf("Erro: Memoria Insuficiente");
			return NULL;
		}
	}
	return v; 
}

int *aloca_vetor(int m) {
	int *v; 

	if (m < 1) { 
		printf("Erro: Parametro invalido");
		return NULL;
	}

	v = (int*) malloc (m * sizeof(int));
	if (v == NULL) {
		printf("Erro: Memoria Insuficiente");
		return NULL;
	}

	return v;
}


int main(void) {
	int m, k;
	int i, j;
	int **v;
	int *p;
	
	int maior, menor, maior_i, maior_j, menor_i, menor_j;
	int maior_pi, maior_pi_i, menor_pi,menor_pi_i;
	int desvio_padrao, media;

	srand(time(NULL));
	
	while(1) {
		printf("\nEntre com as dimensões da matriz: ");
		scanf ("%d %d", &m, &k);
		
		if ((m == 0 && k == 0) || (m != k)) break;

		// Guardando o tempo de iníicio
		double ini = time(0); 		

		v = aloca_matriz(m, k);
		p = aloca_vetor(m);

		// Gerando matriz aleatoria -100 a +100
		for(i = 0; i < m; i++) {
			for(j = 0; j < k; j++) {
				v[i][j] = (rand() % 201) - 100; 
			}
			p[i] = 0;
		}

		menor = v[0][0];
		maior = v[0][0];
		maior_i = 0;
		maior_j = 0;
		menor_i = 0;
		menor_j = 0;
		media = 0;
		
		// Calculando oo maior e o menor, e o produto interno
		for(i = 0; i < m; i++) {
			for(j = 0; j < k; j++) {
				if (v[i][j] > maior) {
					maior = v[i][j];
					maior_i = i;
					maior_j = j;
				}
				if (v[i][j] < menor) {
					menor = v[i][j];
					menor_i = i;
					menor_j = j;
				}
				p[i] += v[i][j] * v[j][i]; 
			}
			media += p[i];
		}
		media /= m; 
		
		menor_pi = p[0];
		maior_pi = p[0];
		maior_pi_i = 0;
		menor_pi_i = 0;
		desvio_padrao = 0;

		// Calculando o maior e o menor pi
		for(i = 0; i < m; i++) {
			desvio_padrao += pow((p[i] - media), 2); 
			if (p[i] > maior_pi) {
				maior_pi = p[i];
				maior_pi_i = i;
			}
			if (p[i] < menor_pi) {
				menor_pi = p[i];
				menor_pi_i = i;
			}
		}	

		// Calculando o desvio padrão
		desvio_padrao = sqrt(desvio_padrao / (m-1));


		// Imprimindo os resultados
		/*
		printf("\n--------------------\n");
		printf("matriz\n");
		
		for(i = 0; i < m; i++) {
			for(j = 0; j < k; j++) {
				printf("%d ", v[i][j]); 
			}
			printf("\n");
		} 

		printf("\n--------------------\n");
		
		printf("Maior: %d em (%d, %d)\n", maior, maior_i, maior_j);
		printf("Menor: %d em (%d, %d)\n", menor, menor_i, menor_j);
		
		printf("\n--------------------\n");
		
		printf("vetor produto interno\n");
		for(i = 0; i < m; i++) {
			printf("%d ", p[i]); 
		}
		printf("\n");
		
		printf("\n--------------------\n");	
		printf("Maior PI: %d em (%d)\n", maior_pi, maior_pi_i);
		printf("Menor PI: %d em (%d)\n", menor_pi, menor_pi_i);
		printf("Desvio Padrão: %d \n", desvio_padrao);
		*/
	
	 	printf("\n--------------------\n");
	    printf("Utilizando algoritmo sequencial com m = k = %d\n", m);

		libera_matriz(m, k, v);
		free(p);
		
		printf("\n--------------------\n");
		printf("Tempo de Execucao: %f segundos\n", time(0) - ini);
 	}

	return 0;
}

